此题线段树模板题，但是据说这题本来要卡线段树但是失败了，正解是树状数组，树状数组快一半，常数小，树状数组区间修改区间查询看我的算法笔记中的解释。
线段树：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "MoSQL"
using namespace std;
const int MAXN = 1e6 + 5;
int n, Q;
LL a[MAXN * 4], sumv[MAXN * 4], addv[MAXN * 4];
#define lc (o<<1)
#define rc (o<<1|1)
#define M ((l+r)>>1)
void pushup(int o) {
sumv[o] = sumv[lc] + sumv[rc];
}
void build(int o, int l, int r) {
if (l == r) sumv[o] = a[l]; else build(lc, l, M), build(rc, M + 1, r), pushup(o);
}
void pushdown(int o, int len) {
if (addv[o]) {
sumv[lc] += addv[o] * (len - len / 2), sumv[rc] += addv[o] * (len / 2);
addv[lc] += addv[o], addv[rc] += addv[o];
addv[o] = 0;
}
}
void update(int o, int l, int r, int x, int y, LL w) {
if (x <= l && r <= y) {
sumv[o] += w * (r - l + 1);
addv[o] += w;
return ;
}
pushdown(o, r - l + 1);
if (x <= M) update(lc, l, M, x, y, w);
if (M < y) update(rc, M + 1, r, x, y, w);
pushup(o);
}
LL query(int o, int l, int r, int x, int y) {
LL ret = 0;
if (x <= l &&r <= y) {
return sumv[o];
}
pushdown(o, r - l + 1);
if (x <= M) ret += query(lc, l, M, x, y);
if (M < y) ret += query(rc, M + 1, r, x, y);
return ret;
}
void clean() {
for (int i=0;i<=n*4;i++) sumv[i] = addv[i] = 0;
}
void solve() {
clean();
for (int i=1;i<=n;i++) scanf("%I64d", &a[i]);
build(1, 1, n);
scanf("%d", &Q);
char ch[20];
for (int i=1;i<=Q;i++) {
scanf("%s", ch);
if (ch[0] == 'Q') {
int l, r;
scanf("%d%d", &l, &r);
if (l > r) swap(l, r);
printf("%I64d\n", query(1, 1, n, l, r));
} else if (ch[0] == 'A') {
int l, r;
LL x;
if (l > r) swap(l, r);
scanf("%d%d%I64d", &l, &r, &x);
update(1, 1, n, l, r, x);
}
}
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
scanf("%d", &n), solve();
fclose(stdin); fclose(stdout);
return 0;
}
树状数组：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "MoSQL"
using namespace std;
const int MAXN = 1e6 + 5;
int n, Q;
LL a[MAXN], c1[MAXN], c2[MAXN];
int lowbit(int x) {return x&(-x);}
void add(int x, LL w) {
for (int i=x;i<=n;i+=lowbit(i)) {
c1[i] += w, c2[i] += (LL)x * (LL)w;
}
}
LL query(int x) {
LL ret = 0;
for (int i=x;i>0;i-=lowbit(i)) {
ret += (x + 1) * c1[i] - c2[i];
}
return ret;
}
void clean() {
ms(c1, 0), ms(c2, 0);
}
void solve() {
clean();
for (int i=1;i<=n;i++) scanf("%I64d", &a[i]), add(i, a[i]), add(i + 1, -a[i]);
scanf("%d", &Q);
char ch[20];
for (int i=1;i<=Q;i++) {
scanf("%s", ch);
if (ch[0] == 'Q') {
int l, r;
scanf("%d%d", &l, &r);
printf("%I64d\n", query(r) - query(l - 1));
} else if (ch[0] == 'A') {
int l, r;
LL x;
scanf("%d%d%I64d", &l, &r, &x);
add(l, x), add(r + 1, -x);
}
}
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
scanf("%d", &n), solve();
fclose(stdin); fclose(stdout);
return 0;
}
mogician 的 SQL
